HW#1 --- last modified February 17 2019 19:23:02..

Solution set.

Due date: Feb 16

Files to be submitted:
  Hw1.pdf

Purpose: To gain familiarity with the set notations and proofs that will be needed for this course. To get familiar with the definition of a formal language. To build our first finite automata.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(2) Construct deterministic and non-deterministic machines for various languages.

Specification:You need a MathML compatible browser to view this page. For this homework, you should do the following exercises, writing them up in a file Hw1.pdf. Remember the maximum file upload size is 2MB so make sure to use compressed graphics.

1. Let `A = {1, 2, 4, 5}` and `B = {3, 4, 6}`. Write out fully the elements in each of the following sets (a) `A \cap B` (b) `B - A` (c) `S(A)` (d) `2^B` (e) `A times B`. Give the cardinality of each set.
2. Prove by induction, that for all `n`, `|P(S^n(emptyset))| = 2^n`.
3. Show using only the properties (a)-(d) of this slide that `S^4(0) cdot S^5(0) = S^{20}(0).
4. Construct using `^^`, `vv`, `not` gates a boolean function `{0, 1}^4 rightarrow {0, 1}` which returns `1` if and only if exactly half of the boolean inputs are `1`.
5. Consider problem 1.1 in the book. Let `M'_1` and `M'_2` be the machines obtained from `M_1` and `M_2` where `q_3` is made an accept state and `q_2` is not an accept state. Answer (a)-(e) of this problem with respect to `M'_1` and `M'_2`. Then give the formal definition of `M'_1` and `M'_2`

Point Breakdown